import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    private List<List<Integer>> lists = new ArrayList<>();
    private LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) return new ArrayList<>();
        recur(root, sum);
        return lists;
    }

    private void recur(TreeNode root, int k) {
        if (root != null) {
            list.add(root.val);
            k -= root.val;
            if (k == 0 && root.left == null && root.right == null) { // 尾结点要是叶子节点
                lists.add(new ArrayList<>(list));
                // 特别注意，这里不能加returnn语句，如果这个地方return的话，下面的removeLast就会执行不到
                // 如果是用的模拟值传递的方式来做的话可以加return
            }
            recur(root.left, k);
            recur(root.right, k);
            list.removeLast();
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        TreeNode tree1 = new TreeNode(1);
        TreeNode tree5 = new TreeNode(5);
        TreeNode tree2 = new TreeNode(2);
        TreeNode tree7 = new TreeNode(7);
        TreeNode tree4_2 = new TreeNode(4);
        TreeNode tree13 = new TreeNode(13);
        TreeNode tree11 = new TreeNode(11);
        TreeNode tree8 = new TreeNode(8);
        TreeNode tree4 = new TreeNode(4);
        TreeNode tree = new TreeNode(5);
        tree.left = tree4;
        tree.right = tree8;
        tree4.left = tree11;
        tree11.left = tree7;
        tree11.right = tree2;
        tree8.left = tree13;
        tree8.right = tree4_2;
        tree4_2.left = tree5;
        tree4_2.right = tree1;
        System.out.println(s.pathSum(tree, 22));
    }
}
